package com.chj.jz.dp.class01;

//https://www.lintcode.com/problem/unique-paths/description
public class Code02_UniquePaths {

	public static int uniquePaths(int m, int n) {
		int[][] f = new int[m][n];
		int i, j;

		for (i = 0; i < m; i++) {
			for (j = 0; j < n; j++) {
				if (i == 0 || j == 0) {
					f[i][j] = 1;
					continue;
				}

				f[i][j] = f[i][j - 1] + f[i - 1][j];
			}
		}

		return f[m - 1][n - 1];
	}
	
	public static void main(String[] args) {
		{
			int m = 3;
			int n = 1;
			System.out.println(uniquePaths(m, n));
		}
		{
			int m = 3;
			int n = 3;
			System.out.println(uniquePaths(m, n));
		}
	}
}
